package CodeTop.有效的括号;

import java.util.Map;
import java.util.Stack;

// https://leetcode.cn/problems/valid-parentheses/
class Solution {
    // 单个栈
    public boolean isValid(String s) {
        var map = Map.of('(', ')', '{', '}', '[', ']');
        var stack = new Stack<Character>();
        
        for (char c : s.toCharArray()) {
            // 遇到左括号则入栈
            if (c == '(' || c == '[' || c == '{') stack.push(c);
            else { // 遇到右括号，判断是否与栈顶匹配
                if (stack.isEmpty()) return false; // 栈中无元素，必然无法匹配
                var item = stack.pop();
                if (map.get(item) != c) return false;
            }
        }
        return stack.isEmpty();
    }

    // 放一对括号入栈
    public boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }

    // 简化代码
    public boolean isValid2(String s) {
        var map = Map.of('(', ')', '{', '}', '[', ']');
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) stack.push(map.get(c));
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }

    // 字符串替换
    public boolean isValid3(String s) {
        int len = s.length() / 2;
        for (int i = 0; i < len; i++) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }
        return s.length() == 0;
    }
}